In this note we provide a concise report on the complexity of the causalordering problem, originally introduced by Simon to reason about causaldependencies implicit in systems of mathematical equations. We show thatSimon's classical algorithm to infer causal ordering is NP-Hard---anintractability previously guessed but never proven. We present then a detailedaccount based on Nayak's suggested algorithmic solution (the best available),which is dominated by computing transitive closure---bounded in time by$O(|\mathcal V|\cdot |\mathcal S|)$, where $\mathcal S(\mathcal E, \mathcal V)$is the input system structure composed of a set $\mathcal E$ of equations overa set $\mathcal V$ of variables with number of variable appearances (density)$|\mathcal S|$. We also comment on the potential of causal ordering foremerging applications in large-scale hypothesis management and analytics.
展开▼
机译:在本说明中,我们提供了因果排序问题的复杂性的简明报告,最初是由Simon提出的,用于推理数学方程系统中隐含的因果依赖关系。我们证明了西蒙推论因果排序的经典算法是NP-Hard ---一种先前猜测但从未得到证明的难解性。然后,我们根据Nayak提出的算法解决方案(目前可用的最佳算法)提出一个详细的帐目,该方法以计算传递闭包为主导-时间限制为$ O(| \ mathcal V | \ cdot | \ mathcal S |)$,其中$ \ mathcal S(\ mathcal E,\ mathcal V)$是输入系统结构,由一组方程组$ \ mathcal E $覆盖一组$ \ mathcal V $变量(具有变量出现次数(密度))$ | \数学S | $。我们还对因果排序在大规模假设管理和分析中新兴应用的潜力进行了评论。
展开▼